package com.base.graph;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * @ClassName: AllPathsSourceTarget
 * @Description: 797. 所有可能的路径
 * <p>
 * 给你一个有n个节点的 有向无环图（DAG），请你找出所有从节点 0到节点 n-1的路径并输出（不要求按特定顺序）
 * <p>
 * 二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。
 * <p>
 * 译者注：有向图是有方向的，即规定了 a→b 你就不能从 b→a 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/all-paths-from-source-to-target
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @author: li
 * @Date: 2021/8/25 5:20 下午
 */
public class AllPathsSourceTargetDFS {


    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        // 存储结果
        List<List<Integer>> ret = new LinkedList<>();
        // 深度搜索的栈
        Deque<Integer> stack = new LinkedList<>();
        //图中结点个数
        int n = graph.length;
        if (n == 0) {
            return ret;
        }

        dfs(graph, 0, n - 1, ret, stack);
        return ret;

    }

    /**
     * 深度优先搜索
     *
     * @param graph 邻接表（有向无环图DAG）
     * @param start 开始结点
     * @param end   终止结点
     */
    public void dfs(int[][] graph, int start, int end, List<List<Integer>> ret, Deque<Integer> stack) {
            // 添加结点
            stack.addLast(start);
            if (start == end){
                ret.add(new LinkedList<>(stack));
                return;
            }
        for (int x :
                graph[start]) {
            dfs(graph, x, end, ret, stack);
            // 删除结点，回溯
            stack.removeLast();
        }

    }


}
